백준 27172번

오늘 풀어본 문제는 백준의 27172번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

게임을 시작하기 전 각 플레이어는 $1$부터 $1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 $0$ 이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
승리한 플레이어는 $1$ 점을 획득하고, 패배한 플레이어는 $1$ 점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.

《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

입력

첫 번째 줄에 플레이어의 수 $N$이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터 $N$ 번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 $x_{1}$, $\cdots$, $x_{N}$ 이 공백으로 구분되어 주어집니다.

출력

첫 번째 플레이어부터 $N$ 번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

제한

$2 \le N \le 100\,000$
모든 $1 \le i \le N$에 대해 $1 \le x_i \le 1\,000\,000$입니다.
모든 $1 \le i < j \le N$에 대해 $x_i \ne x_j$입니다. 즉, 어떤 수도 $x$에서 두 번 이상 등장하지 않습니다.

풀이과정

1번째 시도

문제를 보고 각 쌍별로 테스트하는 것은 시간복잡도가 $O(n^2)$ 이 되어 시간초과가 발생할 것이라는 것을 알 수 있었다. 시간 초과를 발생시키지 않기 위해 사용한 방법은 다음과 같다.

카드를 입력 받는다.
거대한 1차원 배열을 준비한 뒤, 각 카드별로 자신의 배수가 되면서 카드중에 존재하는 값인 인덱스에 저장된 값을 $1$ 씩 빼고, 그 때마다 해당 카드의 값을 인덱스로 가지는 값에 $1$을 더한다.
최종적으로 각 카드를 인덱스로 하는 값들을 출력한다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    int maximum = INT_MIN;
    vector<int> cards(N, 0);
    unordered_set<int> cardCheck;

    for (int i=0; i<N; i++) {
        int temp;
        cin >> temp;

        maximum = max(maximum, temp);
        cards[i] = temp;
        cardCheck.insert(temp);
    }

    vector<int> numbers(maximum + 1, 0);

    for (auto& card : cards) {
        for (int i=card*2; i<=maximum; i+=card) {
            if (cardCheck.find(i) != cardCheck.end()) {
                numbers[i]--;
                numbers[card]++;
            }
        }
    }

    for (auto& card : cards) {
        cout << numbers[card] << " ";
    }

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

또 해시테이블의 도움을 받았다. PS를 하면서 가장 짜릿한 순간은 해시테이블을 사용해서 시간 복잡도를 회피해버릴 때 인 것 같다. CLASS 5 에서도 통하는 해시테이블… 과연 언제까지 쓸 수 있을까? 앞으로도 계속 이 손맛을 느껴보고 싶은데 과연 가능할까?

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/27172

← Previous Post Next Post →